package leetcode.all;

import leetbook.stack.Solution227_1;

import java.util.Stack;

public class Solution316 {

    public static void main(String[] args) {
        String s = "abacb";
        System.out.println(new Solution316().removeDuplicateLetters(s));
    }

    public String removeDuplicateLetters(String s) {
        int[] count = new int[26]; //记录小写字符出现的次数
        boolean[] isAdd = new boolean[26]; //记录字符是否已经添加
        Stack<Character> stack = new Stack<>(); //单调栈

        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            int idx = cur - 'a';
            count[idx]--; //剩余数量-1
            if(isAdd[idx]) continue; //已经有了
            if (stack.isEmpty()||stack.peek() < cur) { //栈空 或者 栈不空且栈顶元素小于cur
                stack.push(cur);
                isAdd[idx] = true;
            } else { //栈不空，栈顶元素大于cur
                // 栈顶较大而且后面还有剩余确定则出栈
                while (!stack.isEmpty() && stack.peek() > cur && count[stack.peek() - 'a'] > 0) {
                    isAdd[stack.pop() - 'a'] = false;
                }
                stack.push(cur);
                isAdd[idx] = true;
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.insert(0,stack.pop());
        return sb.toString();
    }
}
